package medium;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2022/1/13 17:37
 */
public class No63_不同路径II {
    public static void main(String[] args) {
        Solution63 solution63 = new Solution63();
        int[][] obstacleGrid = new int[][]{
                {0, 0, 0},
                {0, 1, 0},
                {0, 0, 0}
        };
        int i = solution63.uniquePathsWithObstacles(obstacleGrid);
        System.out.println(i);
    }
}

class Solution63 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //一维数组
        //利用动态规划方程,空间缩小
        int x = obstacleGrid.length;
        int y = obstacleGrid[0].length;
        int[] dp = new int[y];
        int diedai = x;
        
        //"动态规划"初始化
        if (obstacleGrid[0][0] == 1) {
            dp[0] = 0;
        } else {
            dp[0] = 1;
        } 
        
        //疯狂迭代获取值
        for (int i = 0; i < diedai; i++) {
            //迭代次数
            //每次迭代,由于有障碍物,因此不能跟上上节一样从1开始
            for (int j = 0; j < y; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                    continue;
                }
                if (j - 1 >= 0) {
                    //方程式
                    dp[j] = dp[j - 1] + dp[j];
                }
            }
        }
        return dp[y - 1];
    }
}



    //public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    //    //动态规划
    //    int hang = obstacleGrid.length;
    //    int lie = obstacleGrid[0].length;
    //    //定义动态规划dp
    //    int[][] dp = new int[hang][lie];
    //    dp[0][0] = 1;
    //    
    //    //遍历循环获取每一个格子的路径条
    //    for (int x = 0; x < hang; x++) {
    //        for (int y = 0; y < lie; y++) {
    //            if (obstacleGrid[x][y] == 1) {
    //                dp[x][y] = 0;
    //                continue;
    //            }
    //
    //            if (x - 1 >= 0) {
    //                dp[x][y] = dp[x - 1][y];
    //            }
    //            if (y - 1 >= 0) {
    //                dp[x][y] += dp[x][y - 1];
    //            }
    //        }
    //    }
    //    return dp[hang - 1][lie - 1];
    //}
